package 数据结构.树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-04
 */
public class JZ34二叉树中和为某一值的路径2 {
    //深度优先搜索 dfs
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }
    void dfs(TreeNode root, int number) {
        // 处理树为空
        if (root == null) return;
        // 路径更新
        path.add(root.val);
        // number更新
        number -= root.val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
        if(root.left == null && root.right == null && number == 0) {
            ret.add(new ArrayList<>(path));
        }
        // 左右子树递归
        dfs(root.left, number);
        dfs(root.right, number);
        path.removeLast();//删除最后一个元素
    }


    //广度优先遍历 队列
    public ArrayList<ArrayList<Integer>> FindPath2(TreeNode root, int expectNumber) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(root == null) return ret;
        Queue<ArrayList<Integer>> pathQ = new LinkedList<ArrayList<Integer>>();
        Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
        pathQ.offer(new ArrayList<Integer>(Arrays.asList(root.val)));
        nodeQ.offer(root);
        while(!nodeQ.isEmpty()) {
            ArrayList<Integer> curpath = pathQ.poll();
            TreeNode curnode = nodeQ.poll();
            if(curnode.left != null) {
                ArrayList<Integer> left = new ArrayList<Integer>(curpath);
                left.add(curnode.left.val);
                pathQ.offer(left);
                nodeQ.offer(curnode.left);
            }
            // 右子节点path
            if(curnode.right != null) {
                ArrayList<Integer> right = new ArrayList<Integer>(curpath);
                right.add(curnode.right.val);
                pathQ.offer(right);
                nodeQ.offer(curnode.right);
            }
            // 叶子节点统计
            if(curnode.left == null && curnode.right == null) {
                ArrayList<Integer> l = curpath;
                int sum = 0;
                for(int i = 0; i < l.size(); i++) {
                    sum = sum + l.get(i);
                }
                if(sum == expectNumber) ret.add(l);
            }
        }
        return ret;
    }
}
